The disclosures herein relate generally to computer systems and more particularly to printed circuit boards for computer systems manufactured with a quasi-Monte Carlo simulation technique for multi-dimensional spaces.
Simulation of multi-dimensional systems is becoming more necessary because of narrower constraints in modern designs. For example, determination of a printed-circuit board's trace impedance usually requires 3 or more dimensions (or parameters), trace width, dielectric height, dielectric constant, trace height, etc. Additional dimensions, such as solder mask thickness and permittivity constant, previously ignored because of their minimal effect in the days of wide constraints, now need to be considered. Each of these dimensions has manufacturing tolerances that affect the error of the impedance.
Simulation methods to determine the range of error on the final solution are needed to answer questions of which parameters are important to monitor or specify, and those parameters that are not. Undue lengthy simulation times pose problems in a manufacturing environment. As the number of dimensions increases, the number of simulation combinations grow geometrically, and can reach astronomical limits if high resolution is required. Accordingly, a need exists to efficiently determine this information within a reasonable simulation time.
In addition, signal integrity simulation may involve complex wiring topologies with multiple trace segments. For example, the combinations of ten (10) trace segments each with ten (10) possible lengths amounts to ten (10) billion possible topologies. It is unwise to methodically simulate every possible combination.
One prior method used is the grid method, briefly mentioned above. With the grid method, each dimension is defined to have a minimum and a maximum value, in addition to having a fixed number of evenly-spaced values in between. If there are ten dimensions that need to be resolved each into 10 points, then the simulation space is 10^10, or 10 billion simulations. Not withstanding the extreme number of combinations, there are areas between the grid points that will never be simulated, which may miss some non-linear anomaly (such as resonance phenomena). FIG. 1 illustrates a graphical view of 5000 grid method points on a 1×1 grid.
A common stochastic method is the classic Monte Carlo technique, where a value for each dimension is randomly picked for each simulation. The Monte Carlo technique allows a smaller sample of values than the grid method, and can be set to obtain off-grid values. However, because of ‘random clumping’ (see FIG. 2), some areas will be redundantly sampled, while others may be ignored due to voids. The Monte Carlo method's error decreases inversely proportional to the square root of the number of samples, and doubling the sampling rate decreases the error by approximately 30%. FIG. 2 illustrates a 2D plot of 5000 Monte Carlo points on a 1×1 grid. Using the Monte Carlo method, undesirable clumping and voiding occur within the grid.
In addition to the Monte Carlo method, there exists a quasi-Monte Carlo method. The quasi-Monte Carlo method is a relatively new method (ca. 1992) that generates a hard-coded point-cloud that substantially evenly covers the dimensional space. The quasi-Monte Carlo method error drops at almost the rate of 1/N for multiple dimensions, wherein doubling the samples halves the error. This is very important in limiting the computations for medium to large dimensions.
A problem with quasi-Monte Carlo method, however, is that a sequence of generated numbers from one base cannot be indexed into the dimensional space without producing very non-random correlations. One accepted technique is to use multiple bases to generate separate quasi-Monte Carlo sequences for each dimension. Base numbers of 2, 3, and 5 are most often used for 3-dimensional work. The problem is that as the base gets larger, the point cloud becomes more sparse.
Accordingly, a need exists for a simulation method to determine a range of error to identify which parameters are important to monitor within a reasonable simulation time.